package ar.com.dridco.homework;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Grafo<E> {

	private ArrayList<Vertice<E>> vertices;
	private Integer[][] matrizAdyacencia;
	private static final Integer INFINITO = 999999;

	public Grafo(ArrayList<Vertice<E>> vertices, Integer[][] matriz) {
		this.vertices = vertices;
		this.matrizAdyacencia = matriz;
	}

	public Integer calcularDistanciaDeRuta(ArrayList<Vertice<E>> ruta) {
		Integer valorRuta = 0;

		Object[] rutaArray = ruta.toArray();
		for (Integer i = 0; i < ruta.size() - 1; i++) {
			try {
				Integer valor = matrizAdyacencia[vertices
						.indexOf((Vertice<E>) rutaArray[i])][vertices
						.indexOf((Vertice<E>) rutaArray[i + 1])];
				if (valor == -1) {
					return -1;
				} else {
					valorRuta += valor;
				}
			} catch (ArrayIndexOutOfBoundsException e) {
				return -1;
			}
		}

		return valorRuta;
	}

	public Integer calcularCantidadDeViajesMenorAMaximo(Vertice<E> desde,
			Vertice<E> hasta, Integer paradasMaximas) {
		Integer[] suma = { 0 };
		recorrerGrafoConViajesMaximos(desde, hasta, paradasMaximas, suma);

		return suma[0];

	}

	public void recorrerGrafoConViajesMaximos(Vertice<E> desde,
			Vertice<E> hasta, Integer paradasMaximas, Integer[] suma) {
		for (Vertice<E> v : vertices) {
			if (matrizAdyacencia[vertices.indexOf(desde)][vertices.indexOf(v)] != -1) {
				if (!v.equals(hasta) && paradasMaximas != 0) {
					recorrerGrafoConViajesMaximos(v, hasta, paradasMaximas - 1,
							suma);
				} else {
					if (v.equals(hasta) && paradasMaximas != 0) {
						suma[0]++;
					}
				}
			}
		}
	}

	public Integer calcularCantidadDeViajesExactos(Vertice<E> desde,
			Vertice<E> hasta, Integer paradasExactas) {
		Integer[] suma = { 0 };
		Integer cantidadParadas = 1;
		recorrerGrafoConViajesExactos(desde, hasta, paradasExactas,
				cantidadParadas, suma);

		return suma[0];
	}

	public void recorrerGrafoConViajesExactos(Vertice<E> desde,
			Vertice<E> hasta, Integer paradasExactas, Integer cantidadParadas,
			Integer[] suma) {
		for (Vertice<E> v : vertices) {
			if (matrizAdyacencia[vertices.indexOf(desde)][vertices.indexOf(v)] != -1) {
				if (cantidadParadas < paradasExactas) {
					recorrerGrafoConViajesExactos(v, hasta, paradasExactas,
							cantidadParadas + 1, suma);
				} else {
					if (v.equals(hasta) && cantidadParadas == paradasExactas) {
						suma[0]++;
					}
				}
			}
		}
	}

	public Integer calcularDistanciaDeRutaMasCorta(Vertice<String> desde,
			Vertice<String> hasta) {

		for (Integer i = 0; i < vertices.size(); i++) {
			for (Integer j = 0; j < vertices.size(); j++) {
				if (matrizAdyacencia[i][j] == -1) {
					matrizAdyacencia[i][j] = INFINITO;
				}
			}
		}

		ArrayList<Integer> costos = new ArrayList<Integer>();
		ArrayList<Integer> s = new ArrayList<Integer>();
		ArrayList<Integer> restante = new ArrayList<Integer>();// v-s
		Vertice<E> w;
		Integer posicion = vertices.indexOf(desde);

		if (vertices.indexOf(desde) < vertices.size()) {

			s.add(posicion);

			for (int i = 0; i < vertices.size(); i++) {
				costos.add(matrizAdyacencia[posicion][i]);
				if (i != vertices.indexOf(desde))
					restante.add(i);
			}

			costos.set(posicion, INFINITO);

			while (!restante.isEmpty()) {

				w = vertices.get(menor(restante, costos));
				s.add(vertices.indexOf(w));

				for (int i = 0; i < vertices.size(); i++) {
					costos.set(
							i,
							minimo(costos.get(i),
									costos.get(vertices.indexOf(w))
											+ matrizAdyacencia[vertices
													.indexOf(w)][i]));
				}

			}

		}

		return costos.get(vertices.indexOf(hasta));
	}

	private Integer minimo(Integer a, Integer b) {
		if (a <= b) {
			return a;
		} else {
			return b;
		}
	}

	private Integer menor(ArrayList<Integer> restante, ArrayList<Integer> costos) {

		Iterator<Integer> it = restante.iterator();

		Integer valor = it.next();
		Integer menor = costos.get(valor);
		Integer posicion = 0;

		Integer i = 1;
		while (it.hasNext()) {
			Integer dato = costos.get(it.next());
			if (menor > dato && dato > 0) {
				menor = dato;
				posicion = i;
			}
			i++;
		}

		Integer a = restante.get(posicion.intValue());
		restante.remove(posicion.intValue());

		return a;
	}

	public Integer calcularCantidadDeRutasDistintas(Vertice<E> desde,
			Vertice<E> hasta, Integer distanciaMaxima) {

		ArrayList<Vertice<E>> caminoTemporal = new ArrayList<Vertice<E>>();
		caminoTemporal.add(desde);

		Queue<ArrayList<Vertice<E>>> cola = new LinkedList<ArrayList<Vertice<E>>>();
		cola.add(caminoTemporal);

		Integer cantidadDeCaminos = 0;

		while (!cola.isEmpty()) {
			caminoTemporal = cola.poll();
			Vertice<E> ultimoNodo = caminoTemporal
					.get(caminoTemporal.size() - 1);

			if (ultimoNodo == hasta) {
				cantidadDeCaminos++;
			}

			for (Vertice<E> v : vertices) {
				if (matrizAdyacencia[vertices.indexOf(ultimoNodo)][vertices
						.indexOf(v)] != -1) {

					ArrayList<Vertice<E>> prueba = new ArrayList<Vertice<E>>();
					prueba.addAll(caminoTemporal);
					prueba.add(v);
					Integer a = calcularDistanciaDeRuta(prueba);

					if (a < distanciaMaxima) {
						ArrayList<Vertice<E>> nuevoCamino = new ArrayList<Vertice<E>>();
						nuevoCamino.addAll(caminoTemporal);
						nuevoCamino.add(v);
						cola.add(nuevoCamino);
					}
				}
			}

		}

		return cantidadDeCaminos - 1;
	}

	public ArrayList<Vertice<E>> getVertices() {
		return vertices;
	}

}
